package q116_connect;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Solution_1 {
    class Node {
        public int val;
        public Node left;
        public Node right;
        public Node next;

        public Node() {}

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _left, Node _right, Node _next) {
            val = _val;
            left = _left;
            right = _right;
            next = _next;
        }
    };

    /**
     * 还是使用广度优先搜索，每次将一层的元素全部poll出来之后，保存到一个list里，然后依次将其连接起来即可
     * 这种方法的时间复杂度比较高
     */
    public Node connect(Node root) {
        if (root == null) {
            return null;
        }

        Queue<Node> q = new LinkedList<Node>();
        q.offer(root);

        List<Node> level = new ArrayList<Node>();
        while (!q.isEmpty()) {
            int curLen = q.size();
            for (int i = 0; i < curLen; i++) {
                Node curNode = q.poll();
                level.add(curNode);
                // 这里由于是一个完美平衡二叉树，所以只需要判断一次
                if (curNode.left != null) {
                    q.offer(curNode.left);
                    q.offer(curNode.right);
                }
            }
            // 结束curlen的循环之后，只需要将list中的相邻元素连接起来即可
            for (int i = 0; i < level.size() - 1; i++) {
                level.get(i).next = level.get(i + 1);
            }
            // 最后要clear
            level.clear();

        }

        return root;

    }

}
